package com.ward.bst;

import java.util.Stack;

/**
 * Created by ward on 2017-09-04.
 */
public class RBTree {
    private class Node {
        private String color;
        private Integer value;
        private Node leftNode;
        private Node rightNode;
        private Node parentNode;

        public String getColor() {
            return color;
        }

        public void setColor(String color) {
            this.color = color;
        }

        public Integer getValue() {
            return value;
        }

        public void setValue(Integer value) {
            this.value = value;
        }

        public Node getLeftNode() {
            return leftNode;
        }

        public void setLeftNode(Node leftNode) {
            this.leftNode = leftNode;
        }

        public Node getRightNode() {
            return rightNode;
        }

        public void setRightNode(Node rightNode) {
            this.rightNode = rightNode;
        }

        public Node getParentNode() {
            return parentNode;
        }

        public void setParentNode(Node parentNode) {
            this.parentNode = parentNode;
        }

        public Node(Integer value, String color, Node leftNode, Node rightNode, Node parentNode) {
            super();
            this.color = color;
            this.value = value;
            this.leftNode = leftNode;
            this.rightNode = rightNode;
            this.parentNode = parentNode;
        }

    }

    private Node rootNode;

    public Node getRootNode() {
        return rootNode;
    }

    public void setRootNode(Node rootNode) {
        this.rootNode = rootNode;
    }

    private Node findInsertParentNode(Integer value) {
        Node currentNode = rootNode;
        Node preCurrentNode = rootNode;
        while (null != currentNode) {
            if (value > currentNode.getValue()) {
                preCurrentNode = currentNode;
                currentNode = currentNode.getRightNode();
            } else {
                preCurrentNode = currentNode;
                currentNode = currentNode.getLeftNode();
            }
        }

        return preCurrentNode;
    }

    private void insertNodeFix(Node currentNode) {
        Node parentNode = currentNode.getParentNode();
        if (null == parentNode) {
            currentNode.setColor("black");
            this.setRootNode(currentNode);
            //插入的几点 为root节点时 注意!!!
            // currentNode.setParentNode(rootNode);
            return;
        }
        Node grandParentNode = parentNode.getParentNode();
        if (null == grandParentNode) {
            return;
        }
        //获得叔父节点
        Node uncleNode;
        if (null != grandParentNode.getLeftNode()) {
            uncleNode = parentNode == grandParentNode.getLeftNode() ? grandParentNode.getRightNode() : grandParentNode.getLeftNode();
        } else {
            uncleNode = null;
        }

        if ("black".equals(parentNode.getColor())) {  //父节点 为黑色
            return;
        } else if ("red".equals(parentNode.getColor())) {//父节点为 红色
            //叔父节点 为NULL 或为 黑色
            if (null == uncleNode || "black".equals(uncleNode.getColor())) {
                Boolean parentLeftGrand = (parentNode == (grandParentNode.getLeftNode())) ? true : false;
                Boolean currentLeftParent = (currentNode == (parentNode.getLeftNode())) ? true : false;
                if (parentLeftGrand && currentLeftParent) {//LL 型
                    parentNode.setColor("black");
                    grandParentNode.setColor("red");
                    this.rightRotate(grandParentNode);
                } else if (parentLeftGrand && !currentLeftParent) {//LR 型
                    currentNode.setColor("black");
                    grandParentNode.setColor("red");
                    this.leftRotate(parentNode);
                    this.rightRotate(grandParentNode);

                } else if (!parentLeftGrand && currentLeftParent) {//RL 型
                    currentNode.setColor("black");
                    grandParentNode.setColor("red");
                    this.rightRotate(parentNode);
                    this.leftRotate(grandParentNode);

                } else if (!parentLeftGrand && !currentLeftParent) {//RR 型
                    parentNode.setColor("black");
                    grandParentNode.setColor("red");
                    this.leftRotate(grandParentNode);
                }
                return;

            } else if ("red".equals(uncleNode.getColor())) {
                parentNode.setColor("black");
                uncleNode.setColor("black");
                grandParentNode.setColor("red");
                this.insertNodeFix(grandParentNode);
            }
        }
        return;

    }


    private void leftRotate(Node currentNode) {
        //当前节点的右孩子
        Node rightChild = currentNode.getRightNode();
        if (null == rightChild) {
            return;
        }
        //当前节点右孩子的左孩子
        Node rLChildNode = rightChild.getLeftNode();


        //当前节点的父节点
        Node parent = currentNode.getParentNode();


        //变更1
        if (null == parent) { //若当前节点 根节点 则会出现为null的情况
            this.setRootNode(rightChild);
            //??? 根节点 不存在 父节点
            rightChild.setParentNode(null);

        } else {
            if (parent.getRightNode() == (currentNode)) {
                parent.setRightNode(rightChild);
            } else {
                parent.setLeftNode(rightChild);
            }
            rightChild.setParentNode(parent);
        }


        //变更2
        rightChild.setLeftNode(currentNode);
        currentNode.setParentNode(rightChild);

        //变更3

        if (null != rLChildNode) {
            rLChildNode.setParentNode(currentNode);
        } else {
            //如果rLChildNode 为NULL 的情况 怎么处理？？
        }
        currentNode.setRightNode(rLChildNode);

        return;
    }

    private void rightRotate(Node currentNode) {
    /*
          parent              parent
            |                   |
            A                   B
           / \                 / \
          B   C    ----->     D   A
         / \                     / \
        D   E                   E   C
        */
        //当前节点的父节点
        Node parent = currentNode.getParentNode();
        //当前节点的左孩子
        Node leftChild = currentNode.getLeftNode();
        if (null == leftChild) {
            //如果为null 则无法进行 右旋转 操作
            return;
        }
        Node lRChild = leftChild.getRightNode(); //当前节点的左孩子的右孩子
        //变更1
        if (null == parent) {
            this.setRootNode(leftChild);
            // ??? 根节点  不存在  父节点
            leftChild.setParentNode(null);
        } else {
            if (parent.getLeftNode() == (currentNode)) {
                //旋转的中心节点  是其父节点的 左孩子
                parent.setLeftNode(leftChild);
            } else {
                //旋转的中心节点  是其父节点的 右孩子
                parent.setRightNode(leftChild);
            }
            leftChild.setParentNode(parent);
        }

        //变更2
        currentNode.setParentNode(leftChild);
        leftChild.setRightNode(currentNode);

        //变更3

        if (null != lRChild) {
            lRChild.setParentNode(currentNode);
            //
        }
        // currentNode.setRightNode(cLRChild);
        currentNode.setLeftNode(lRChild);

    }


    public void insertValue(Integer value) {
        Node insertNode = new Node(value, "red", null, null, null);

        //
        Node insertParentNode = this.findInsertParentNode(value);
        if (null != insertParentNode) {
            if (value > insertParentNode.getValue()) {
                insertParentNode.setRightNode(insertNode);
            } else {
                insertParentNode.setLeftNode(insertNode);
            }
        }
        insertNode.setParentNode(insertParentNode);
        this.insertNodeFix(insertNode);
    }

    /**
     * @param subRoot
     * @desc 递归遍历红黑树
     */

    public void inorderTraversalRecursive(Node subRoot) {
        if (null != subRoot.getLeftNode()) {
            inorderTraversalRecursive(subRoot.getLeftNode());
        }
        System.out.print(subRoot.getValue() + ",");
        if (null != subRoot.getRightNode()) {
            inorderTraversalRecursive(subRoot.getRightNode());
        }
        return;
    }


    /**
     * @param rootNode
     * @desc 中序遍历  左根右  ---非递归实现
     */
    public void inorderTraversal1(Node rootNode) {
        Stack<Node> nodeStack = new Stack<>();
        Node currentNode, prePrintNode = null;
        nodeStack.push(rootNode);
        while (!nodeStack.isEmpty()) {
            currentNode = nodeStack.pop();
            Node leftChildNode = currentNode.getLeftNode();
            Node rightChildNode = currentNode.getRightNode();

            Boolean hasPrintRightGrandson = false, hasPrintLeftSon = false;
            if (null != prePrintNode) {
                hasPrintRightGrandson = (null != prePrintNode.getParentNode() && prePrintNode.getParentNode().getParentNode() == currentNode);
                hasPrintLeftSon = (prePrintNode == leftChildNode);
            }

            if ((null == leftChildNode) || hasPrintLeftSon || hasPrintRightGrandson) {
                System.out.print(currentNode.getValue() + ",");
                prePrintNode = currentNode;
            } else {
                if (null != rightChildNode) {
                    nodeStack.push(rightChildNode);
                }
                nodeStack.push(currentNode);
                if (null != leftChildNode && (prePrintNode == null || prePrintNode.getParentNode() != leftChildNode)) {
                    nodeStack.push(leftChildNode);
                }
            }
        }
        return;
    }

    /**
     * @param rootNode
     * @desc 中序遍历  左根右  ---非递归实现
     */
    public void inorderTraversal2(Node rootNode) {
        Stack<Node> nodeStack = new Stack<>();
        Node tempNode = rootNode;
        while (null != tempNode || !nodeStack.isEmpty()) {
            while (null != tempNode) {
                nodeStack.push(tempNode);
                tempNode = tempNode.getLeftNode();
            }
            if (!nodeStack.isEmpty()) {
               /* tempNode=nodeStack.peek();//查看堆栈顶部的对象，但不从堆栈中移除它。
                System.out.print(tempNode.getValue()+",");
                nodeStack.pop();//移除堆栈顶部的对象，并作为此函数的值返回该对象。*/
                tempNode = nodeStack.pop();//移除堆栈顶部的对象，并作为此函数的值返回该对象。
                System.out.print(tempNode.getValue() + ",");
                tempNode = tempNode.getRightNode();
            }
        }
        return;

    }

    /**
     * @desc 前序遍历----根左右
     */
    public void preorderTraversal(Node rootNode) {
        Stack<Node> nodeStack = new Stack<>();
        Node tempNode = rootNode;
        while (null != tempNode || !nodeStack.isEmpty()) {
            while (null != tempNode) {
                nodeStack.push(tempNode);
                System.out.print(tempNode.getValue() + ",");
                tempNode = tempNode.getLeftNode();
            }
            if (!nodeStack.isEmpty()) {
                tempNode = nodeStack.pop();
                tempNode = tempNode.getRightNode();
            }
        }
        return;

    }

    /**
     * @param rootNode
     * @desc 后序遍历二叉树--（左右根）- 非递归实现---但是返回的数据 不一定是按照大小  规则展示的
     */
    public void postorderTraversal(Node rootNode) {
        Stack<Node> nodeStack = new Stack<>();
        Node currentNode, prePrintNode = null;
        nodeStack.push(rootNode);
        while (!nodeStack.isEmpty()) {
            currentNode = nodeStack.peek();
            Node leftChildNode = currentNode.getLeftNode();
            Node rightChildNode = currentNode.getRightNode();
            if ((null == leftChildNode && null == rightChildNode) ||
                    (null != prePrintNode && (prePrintNode == leftChildNode || prePrintNode == rightChildNode))) {
                System.out.println(currentNode.getValue());
                nodeStack.pop();
                prePrintNode = currentNode;
            } else {
                if (null != rightChildNode) {
                    nodeStack.push(rightChildNode);
                }
                if (null != leftChildNode) {
                    nodeStack.push(leftChildNode);
                }
            }
        }
        return;
    }


    /**
     * @param currentNode
     * @desc 查询二叉树中 某个节点的 前驱节点
     */
    private Node findPrecursorNode(Node currentNode) {
        Node tempNode = currentNode.getLeftNode();
        if (null == tempNode) {
            return null;
        }
        while (null != tempNode.getRightNode()) {
            tempNode = tempNode.getRightNode();
        }
        return tempNode;
    }

    private Node findDeleteNode(Integer value) {
        Node currentNode = rootNode;
        while (null != currentNode) {
            if (value > currentNode.getValue()) {
                currentNode = currentNode.getRightNode();
            } else if (value < currentNode.getValue()) {
                currentNode = currentNode.getLeftNode();
            } else {
                return currentNode;
            }
        }
        return null;
    }

    /**
     * @param value
     * @desc 此处 实际删除的节点 为前驱节点， 前驱节点 必定没有 右孩子
     */
    public void deleteNode(Integer value) {
        Node originDeleteNode = this.findDeleteNode(value);
        if (null == originDeleteNode) {
            System.out.println();
            System.out.println("要删除的值不存在" + value);
            return;
        }
       /* Node currentNode = originDeleteNode;
        Node trueDelNodeLChild = currentNode.getLeftNode();
        Node trueDelNodeRChild = currentNode.getRightNode();*/

        Node currentNode,trueDelNodeLChild,trueDelNodeRChild;
        Node originDelLChild =originDeleteNode.getLeftNode() ;
        Node originDelRChild= originDeleteNode.getRightNode();

        //4.原始要删除的节点，有两个孩子节点
        if (null != originDelLChild && null != originDelRChild) {
            //4.原始要删除的节点，有两个孩子节点
            //先找到前驱节点
            Node precursorNode = this.findPrecursorNode(originDeleteNode);
            //交换原始删除节点 和前驱节点的值
            this.exchangeValue(originDeleteNode, precursorNode);
            //实际被删除的节点为中心点，转化为 情况1、2、3中的一种情况处理
            currentNode = precursorNode;
            trueDelNodeLChild = currentNode.getLeftNode();
            trueDelNodeRChild = currentNode.getRightNode();
            //！注意,后续将判断转化为 1.2.3 中的那种情况.......
        }else{
            //如果不符合 上述的情况，那么原始要删除的节点就是   真实删除的节点就是
             currentNode = originDeleteNode;
             trueDelNodeLChild = originDelLChild;
             trueDelNodeRChild = originDelRChild;
        }

        if (null == trueDelNodeLChild && null == trueDelNodeRChild) {
            //1.原始要删除的节点，没有孩子节点（该节点必定叶子节点）

            Node brotherNode = this.getBrotherNode(currentNode);
            Node parentNode = currentNode.getParentNode();
            if (null == parentNode) {//此时 表示currentNode  为根节点
                this.setRootNode(null);
            }
            Boolean currentLeftParent = (currentNode == parentNode.getLeftNode()) ? true : false;
            currentNode.setParentNode(null);
            if (currentLeftParent) {
                parentNode.setLeftNode(null);
            } else {
                parentNode.setRightNode(null);
            }
            if ("red".equals(originDeleteNode.getColor())) {
                return;
            } else if ("black".equals(originDeleteNode.getColor())) {
                this.deleteNodeFix(parentNode, brotherNode);
                return;
            }

        } else if (null != trueDelNodeLChild && null == trueDelNodeRChild) {
            //2.原始要删除的节点，仅有一个左孩子节点（该左孩子节点必为红色）

            Node leftChildNode = currentNode.getLeftNode();
            Node parentNode = currentNode.getParentNode();
            leftChildNode.setColor("black");
            if (null == parentNode) {
                this.setRootNode(leftChildNode);
                leftChildNode.setParentNode(null);
                return;
            } else {
                Boolean currentLeftParent = (currentNode == parentNode.getLeftNode()) ? true : false;
                if (currentLeftParent) {
                    leftChildNode.setParentNode(parentNode);
                } else {
                    parentNode.setRightNode(leftChildNode);
                }
                leftChildNode.setParentNode(parentNode);
                return;
            }


        } else if (null == trueDelNodeLChild && null != trueDelNodeRChild) {
            //3.原始要删除的节点，仅有一个右孩子节点（该右孩子节点必为红色）

            Node rightChildNode = currentNode.getRightNode();
            Node parentNode = currentNode.getParentNode();
            rightChildNode.setColor("black");
            if (null == parentNode) {
                this.setRootNode(rightChildNode);
                rightChildNode.setParentNode(null);
            } else {
                Boolean currentLeftParent = (currentNode == parentNode.getLeftNode()) ? true : false;
                if (currentLeftParent) {
                    parentNode.setLeftNode(rightChildNode);
                } else {
                    parentNode.setRightNode(rightChildNode);
                }
                rightChildNode.setParentNode(parentNode);
                return;
            }
        }


        return;
    }

    /**
     * @param parentNode  真实要删除的节点的父节点
     * @param brotherNode 真实要删除的节点的兄弟节点 currentNode 真实要删除的节点， 该节点 最多只有一个叶子节点且该叶子节点是红色的
     * @desc 真实删除的节点  若是其父节点 的左孩子 则 该节点仅
     */
    private void deleteNodeFix(Node parentNode, Node brotherNode) {
        Boolean brotherRightParent = (brotherNode == parentNode.getRightNode()) ? true : false;
        Node leftNephewNode = brotherNode.getLeftNode();
        Node rightNephewNode = brotherNode.getRightNode();
        if (brotherRightParent) {//兄弟节点 是其父节点的右孩子,则其是左孩子
            if ("black".equals(brotherNode.getColor())) {

                if (null != leftNephewNode && null == rightNephewNode) {
                    //2兄弟节点是黑色、且仅有一个 左侄子
                    brotherNode.setColor(parentNode.getColor());
                    leftNephewNode.setColor("black");

                    this.rightRotate(brotherNode);
                    this.leftRotate(parentNode);
                    return;

                } else if (null != rightNephewNode) {
                    //1兄弟节点是黑色、且仅有一个 右侄子
                    //3兄弟节点是黑色、有两个侄子
                    brotherNode.setColor(parentNode.getColor());
                    parentNode.setColor("black");
                    rightNephewNode.setColor("black");
                    this.leftRotate(parentNode);
                    return;
                } else if (null == rightNephewNode && null == leftNephewNode) {
                    //4兄弟节点是黑色，且没有两个侄子    (此时： 以parent 为根节点的子树 的黑高 已经发生改变)
                    brotherNode.setColor("red");
                    parentNode.setColor("black");
                    if (null == parentNode.getParentNode()) {
                        // parentNode.setColor("black");//?????
                        return;
                    }

                   /* brotherNode = getBrotherNode(parentNode.getParentNode());
                    this.deleteNodeFix(parentNode.getParentNode(), brotherNode);*/
                    //？？？？？此处进行了修改  parentNode.getParentNode 改成 parentNode

                    brotherNode = getBrotherNode(parentNode); //此处取到的父节点的兄弟节点  一定的为非空？？ 待论证!!
                    this.deleteNodeFix(parentNode, getBrotherNode(parentNode));
                    return;

                }


            } else if ("red".equals(brotherNode.getColor())) {
                brotherNode.setColor("black");
                leftNephewNode.setColor("red");
                this.leftRotate(parentNode);
                return;
            }
        } else {
            if ("black".equals(brotherNode.getColor())) {

                if (null == leftNephewNode && null != rightNephewNode) {
                    //2兄弟节点是黑色、且仅有一个 右侄子
                    brotherNode.setColor(parentNode.getColor());
                    rightNephewNode.setColor("black");
                    this.leftRotate(brotherNode);
                    this.rightRotate(parentNode);

                    return;

                } else if (null != leftNephewNode) {
                    //1兄弟节点是黑色、且仅有一个 左侄子
                    //3兄弟节点是黑色、有两个侄子
                    brotherNode.setColor(parentNode.getColor());
                    parentNode.setColor("black");
                    leftNephewNode.setColor("black");
                    this.rightRotate(parentNode);

                    return;
                } else if (null == rightNephewNode && null == leftNephewNode) {
                    //4兄弟节点是黑色，且没有两个侄子    (此时： 以parent 为根节点的子树 的黑高 已经发生改变)

                    brotherNode.setColor("red");
                    parentNode.setColor("black");//??????
                    if (null == parentNode.getParentNode()) {
                        //parentNode.setColor("black");//????
                        return;
                    }
                    //此处取到的兄弟节点  一定的为非空？？ 待论证!!
                    /*brotherNode = getBrotherNode(parentNode.getParentNode());
                    this.deleteNodeFix(parentNode.getParentNode(), brotherNode);*/
                    //brotherNode = getBrotherNode(parentNode);
                    this.deleteNodeFix(parentNode, getBrotherNode(parentNode));
                    return;


                }


            } else if ("red".equals(brotherNode.getColor())) {
                //注意 该结论的前置操作是：删除的当前节点 是黑色的
                //结论: 兄弟节点是红色的，则该兄弟节点 必定有两个孩子且为黑色？？ 需要论证

                brotherNode.setColor("black");
                rightNephewNode.setColor("red");
                this.rightRotate(parentNode);
                return;
            }
        }


    }

    /**
     * @param currentNode 当前节点
     * @desc 获得当前节点的兄弟节点
     */
    private Node getBrotherNode(Node currentNode) {
        Node parentNode = currentNode.getParentNode();
        if (null == parentNode) {
            return null;
        }
        Node brotherNode = (currentNode == parentNode.getLeftNode()) ? parentNode.getRightNode() : parentNode.getLeftNode();
        return brotherNode;
    }

    private void exchangeValue(Node delNode, Node preNode) {
        Integer temp = delNode.getValue();
        delNode.setValue(preNode.getValue());
        preNode.setValue(temp);
    }

    public static void main(String[] args) {
        RBTree rbTree = new RBTree();
        Integer[] valueArr = {9, 19, 8, 20, 28, 4545, 88, 98, 25, 456, 7, 6, 5, 4};
        for (int i = 0; i < valueArr.length; i++) {
            System.out.println("开始插入" + valueArr[i]);
            rbTree.insertValue(valueArr[i]);
            System.out.println("插入结束" + valueArr[i]);
        }
        System.out.println();
        System.out.println("---------------------------");
        rbTree.inorderTraversal2(rbTree.getRootNode());
        System.out.println();
        System.out.println("---------------------------");
        rbTree.inorderTraversalRecursive(rbTree.getRootNode());
        System.out.println();
        System.out.println("---------------------------");
        rbTree.preorderTraversal(rbTree.getRootNode());

       /* System.out.println();
        System.out.println("---------------------------");
        rbTree.deleteNode(19);
        rbTree.deleteNode(9);
        rbTree.deleteNode(4);
        rbTree.deleteNode(6);
        //System.out.println("---------------------------");
        rbTree.deleteNode(8);
        rbTree.inorderTraversalRecursive(rbTree.getRootNode());
        System.out.println();
        rbTree.deleteNode(4545);
        rbTree.inorderTraversalRecursive(rbTree.getRootNode());
        System.out.println();
*/

    }


}
